Tree

发表于 | 分类于 | 
1
2
3
4
5
6
7
8
9
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

94. 中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;

    while(curr!=null || !stack.isEmpty()){
        if(curr != null){
            stack.add(curr);
            curr = curr.left;
        }else{
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
    }

    return res;
}

144. 前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (!stack.isEmpty() || curr != null){
        if(curr != null){
            stack.add(curr);
            res.add(curr.val);
            curr = curr.left;
        }else{
            curr = stack.pop();
            curr = curr.right;
        }
    }

    return res;
}

145. 后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (!stack.isEmpty() || curr != null){
        if(curr != null){
            stack.add(curr);
            res.add(curr.val);
            curr = curr.right;
        }else{
            curr = stack.pop();
            curr = curr.left;
        }
    }

    Collections.reverse(res);

    return res;
}